Arrays case study:

1. Searching:

Finding a target element within a search pool (array)

arr:	1	5	7	10	12
target: 11

Algorithm#1: Linear search
- Linear search
Time complexity for linear search: O(n) where n is the size of the pool


- binary search

Very important to keep in mind: "We do binary search only if the pool is sorted" - COE 211

Application#1: SearchingApp.java 	middle
target: 11				left
				right
idxes:  0	1	2	3	4
values: 1	5	7	10	12

boolean found = false;
As long as the target is not found and left is still less than or equal to right
int middle = (left + right) / 2;
if(pool[middle] == target) {
	found = true;
} else if(pool[middle] < target) {
	left = middle + 1;
} else {
	right = middle - 1;
}

binary search: O(log2(n)) if n is the size of the pool
- Why is it a bad idea to sort the values and then perform binary search:

1. Sorting (O(n log2(n))
2. Searching (O(log2(n))
---------------------------
Overall time complexity: O(n log2(n))

2. Sorting:
arr:
5	1	10	2

Selection sort:
1	5	10	2
1	2	10	5
1	2	5	10

1 + 2 + 3 + ... + n - 1 = n ( n - 1) / 2 = O(n^2)

For every position in the array find the value that should occupy that position in the sorted 
version of the array. 

I wish I could do it for the first position only (Wishful thinking)

Simpler version of the problem: Let the smallest value in the array occupy the first position

int idx = 0;

int idxMin = idx;
for(int scan = idx + 1; scan < arr.length; scan++) {
	if(arr[scan] < arr[idxMin]) { idxMin = scan; }
}
// idxMin is the idx of the smallest value in the array
swap(arr, idx, idxMin);

To do it for all the positions of the array: 
for(int idx = 0; idx < arr.length - 1; idx++) {
int idxMin = idx;
for(int scan = idx + 1; scan < arr.length; scan++) {
	if(arr[scan] < arr[idxMin]) { idxMin = scan; }
}
// idxMin is the idx of the smallest value in the array
swap(arr, idx, idxMin);
}

















